package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code2
 * @Description 二维数组的查找
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 示例:
 * <p>
 * 现有矩阵 matrix 如下：
 * <p>
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 * <p>
 * 给定 target = 20，返回 false。
 * <p>
 *  
 * <p>
 * 限制：
 * 0 <= n <= 1000
 * 0 <= m <= 1000
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-07 18:35
 */
public class Code2 {
    public static void main(String[] args) {
        int[][] arr = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println(findNumberIn2DArray(arr, 13));
    }
        public static boolean findNumberIn2DArray ( int[][] matrix, int target){
        /*
        遍历每一行的最后一个元素，直到某一行的最后一个元素大于或等于目标值
        */
            int i = 0;
            if (matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            for (; i < matrix.length; i++) {
                if (matrix[i][matrix[i].length - 1] >= target) {
                    break;
                }
            }
            for (int j = i; j < matrix.length; j++) {
                if (binarySearch(matrix[j], target)) {
                    return true;
                }
            }
            return false;
        }

        public static boolean binarySearch ( int[] arr, int target){
            int left = 0;
            int right = arr.length - 1;
            while (left < right) {
                if (target == arr[(left + right) / 2]) {
                    return true;
                }
                if (target < arr[(left + right) / 2]) {
                    right = (left + right) / 2 - 1;
                } else {
                    left = (left + right) / 2 + 1;
                }
            }
            return target == arr[left];
        }
    }
